package algorithm

import scala.collection.mutable.ListBuffer

/**
题目1：腾讯校招面试题：输入一个链表，反转链表后，输出新链表的表头。
 */
class ListItem(){
  var prev:ListItem=_;
  var next:ListItem=_;
  var value:Int=_;

  override def toString: String = {
    "prev:\t"+(if(null!=prev)prev.value else "null")+"\t,value:\t"+value+"\t,next:\t"+(if(null!=next)next.value;else "null")+"\n"
  }
}

class ReversableLinkedList {

  var head:ListItem=_;
  var tail:ListItem=_;

  def reverse(): Unit ={
    var list = this;
    var tempFromHead=list.head;
    var tempFromTail=list.tail;

    //交换头尾节点
    list.head=tempFromTail;
    list.tail=tempFromHead;

    while(tempFromHead.next!=null && tempFromHead != tempFromTail && tempFromHead.prev!=tempFromTail){

      val tempPrev = tempFromHead.prev;
      val tempNext = tempFromHead.next;

      //交换前驱与后置
      tempFromHead.prev = tempFromTail.prev;
      tempFromHead.next = tempFromTail.next;

      tempFromTail.prev = tempPrev
      tempFromTail.next = tempNext

      //修正交换元素的，相邻元素的前驱后置为自己
      if(tempFromHead.prev!=null) {
        tempFromHead.prev.next=tempFromHead;
      }
      if(tempFromHead.next!=null) {
        tempFromHead.next.prev=tempFromHead;
      }

      if(tempFromTail.prev!=null) {
        tempFromTail.prev.next=tempFromHead;
      }
      if(tempFromTail.next!=null) {
        tempFromTail.next.prev=tempFromHead;
      }
    }
  }
  def append(value:Int): Unit ={
    var item:ListItem = new ListItem();
    item.prev=tail;
    item.value=value;

    if(null!=tail) tail.next=item;
    tail=item;

    if(head==null) head=item;
  }

  override def toString: String = {
    val buffer:StringBuffer = new StringBuffer();
    buffer.append("head:"+this.head,"tail:"+this.tail+"\n")
    var temp = this.head;
    while(temp!=null){
      buffer.append("trav:\t"+temp);
      temp=temp.next;
    }
    return buffer.toString;
  }
}
object ReversableLinkedList{
  def main(args: Array[String]): Unit = {
    var list : ReversableLinkedList = new ReversableLinkedList();
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    println("初始化的链表：\n"+list.toString);
    list.reverse();
    println("反转后的链表：\n"+list.toString)
    println("反转后的链表的头节点：\n"+list.head)
  }
}